//移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode* phead=new ListNode(-1);
        phead->next=head;
        ListNode* cur=phead;
        while(cur->next)
        {
            if(cur->next->val==val)
            {
                cur->next=cur->next->next;
            }
            else
            {
                cur=cur->next;
            }
        }
        return phead->next;
    }
};
//反转链表
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        ListNode* next=nullptr;//用来保存 cur->next的一个临时变量
        while(cur)
        {
            //pre cur 
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};
//两两交换链表中的节点
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        ListNode* phead=new ListNode(-1);
        phead->next=head;
        ListNode* cur=phead;
        ListNode* tail=nullptr;
        // cur l1 l2 l3 l4
        while(cur->next && cur->next->next)
        {
            tail=cur->next->next->next;
            ListNode* left=cur->next;
            ListNode* right=cur->next->next;
            cur->next=right;
            right->next=left;
            left->next=tail;
            cur=cur->next->next;
        }
        return phead->next;
    }
};
//删除链表的倒数第 N 个结点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        if(head==nullptr) return nullptr;
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode*cur=dummyHead;
        ListNode*pre=dummyHead;
        while(n--&&cur!=nullptr)
        {
            cur=cur->next;
            if(cur==nullptr) return nullptr;
        }
        //cur再多走一步 当cur->next为空时 pre是要删除的节点的前一个
        cur=cur->next;
        while(cur)
        {
            cur=cur->next;
            pre=pre->next;
        }
        pre->next=pre->next->next;
        return dummyHead->next;
    }
};

//有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) 
    {
        int size1=s.size();
        int size2=t.size();
        if(size1!=size2) return false;
        int arr[26]={0};
        for(int i=0;i<size1;i++)
        {
            arr[s[i]-'a']++;
            arr[t[i]-'a']--;
        }
        for(auto e:arr)
        {
            if(e!=0) return false;
        }
        return true;

    }
};
//两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        //先存把一个nums中的元素存入到哈希表中
        //然后遍历另外一个nums
        //如果在hash中找的到 就把他插入到结果集中
        //结果集需要去重 所以先拿set中转一下
        unordered_set<int>s;
        unordered_set<int>tmp;
        vector<int>res;
        for(auto e:nums1) s.insert(e);
        for(auto e:nums2)
        {
            if(s.find(e)!=s.end())
            {
                tmp.insert(e);
            }
        }
        for(auto it=tmp.begin();it!=tmp.end();it++)
        {
            res.push_back(*it);
        }
        return res;
    }
};
//快乐数
class Solution {
public:
    bool isHappy(int n) 
    {
        unordered_set<int>s;
        while(1)
        {
            n=getvalue(n);
            if(n==1) return true;
            if(s.find(n)!=s.end())
            {
                return false;
            }
            else
            {
                s.insert(n);
            }
        }
        return false;
    }
    //由于判断快乐数的过程 可能是一个无限循环的过程 也就是说
    //如果当某次寻求的过程中出现了和之前一样的数字 
    //那一定不会是快乐数
    int getvalue(int n)
    {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
};